package com.tucc.hello.leetcode.no1_400.no1_200.no41_60.no55;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        //[3,2,1,0,4]
        //[2,3,1,1,4]
        int[] nums = {1, 2, 1, 0};
        System.out.println(solution.canJump(nums));
    }

    public boolean canJump(int[] nums) {
        int ignore = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (ignore <= 0 && nums[i] == 0) {
                return false;
            }
            ignore = Math.max(ignore, nums[i]);
            ignore--;
        }
        return true;
    }

    public boolean canJump2(int[] nums) {
        return canJump(nums, 0);
    }

    public boolean canJump(int[] nums, int cur) {
        if (cur + nums[cur] >= nums.length - 1) {
            return true;
        }
        if (nums[cur] == 0) {
            return false;
        }
        int max = 0;
        int maxIndex = -1;
        for (int i = cur + 1; i <= cur + nums[cur]; i++) {
            if (i + nums[i] >= max && nums[i] != 0) {
                max = nums[i] + i;
                maxIndex = i;
            }
        }
        System.out.println(cur + " " + maxIndex + " " + max);
        if (maxIndex == -1) {
            return false;
        }
        return canJump(nums, maxIndex);
    }
}
